package com.datastructure3.string;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author: 临晖
 * @since: 2024-07-28
 */
public class Solution {

    /**
     *
     * 344. 反转字符串
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     *
     * @param s
     */
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;

        while (left <= right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            left++;
            right--;
        }
    }


    /**
     *
     * 541. 反转字符串 II
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
     * 如果剩余字符少于 k 个，则将剩余字符全部反转。
     * 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
     *
     * @param s
     * @param k
     * @return
     */
    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        for (int i = 0; i < s.length(); i += 2 * k) {

            if (i + k - 1 >= s.length()) {
                reverseRadius(arr, i, s.length());
            } else {
                reverseRadius(arr, i, i + k - 1);
            }
        }

        return new String(arr);
    }



    /**
     *
     * 151. 反转字符串中的单词
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
     * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
     * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
     * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
     *
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        char[] arr = s.toCharArray();

        int lastIndex = 0;
        int fastIndex = 0;

        for (; fastIndex < s.length(); fastIndex++) {
            //如果是字母
            if (arr[fastIndex] != ' ') {
                arr[lastIndex++] = arr[fastIndex];
            }

            //如果是空格，上一个是字母
            if (fastIndex > 0 && arr[fastIndex] == ' ' && arr[fastIndex - 1] != ' ') {
                arr[lastIndex++] = arr[fastIndex];
            }
        }

        lastIndex--;
        if (arr[lastIndex] == ' ') {
            lastIndex--;
        }

        char[] newArrays = Arrays.copyOfRange(arr, 0, lastIndex + 1);

        int worldIndex = 0;
        reverseRadius(newArrays, worldIndex , newArrays.length - 1);

        for (int i = 0; i <= newArrays.length; i++) {
            if (i == newArrays.length || newArrays[i] == ' ') {
                reverseRadius(newArrays, worldIndex, i - 1);
                worldIndex = i + 1;
            }
        }


        return new String(newArrays);
    }

    public void reverseRadius(char[] s, int left, int right) {

        while (left <= right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            left++;
            right--;
        }
    }


    /**
     *
     * 28. 找出字符串中第一个匹配项的下标
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {

        int j =  0;

        //获取前缀表
        int[] next = new int[needle.length()];
        getNext(next, needle);

        //开始遍历
        for (int i = 0; i < haystack.length(); i++) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;

                if (j == needle.length()) {
                    return i - j + 1;
                }
            } else if (j > 0) {
                i--;
                j = next[j - 1];
            }


        }


        return -1;
    }


    //todo 获取前缀表
    public void getNext(int[] next, String str) {
        int j = 0;

        //初始化
        next[0] = 0;
        for (int i = 1; i < str.length(); i++) {

            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = next[j - 1];
            }

            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }


    /**
     *
     * 459. 重复的子字符串
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
     *
     *
     * @param s
     * @return
     */
    public boolean repeatedSubstringPattern(String s) {

        //获取前缀表
        int[] next = new int[s.length()];
        getNext(next, s);

        if (s.length() % (s.length() - next[s.length() - 1]) == 0 && next[s.length() - 1] != 0) {
            return true;
        }
        return false;
    }


    @Test
    public void myTest() {
        String str1 = "abababababababab";
        repeatedSubstringPattern(str1);
    }
}
